#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>

#include "set_cover.h"
#include "vertex_cover.h"
#include "improved_vertex_cover.h"

using std::string;
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::setw;
using std::list;
using std::vector;
using std::priority_queue;

/**
 * Naming Conventions:
 *   rowv usually means row vector
 *   rowi usually means row index or row iterator
 *   rowvi would be an iterator over row vectors
 *   variables with end in the name are used as < terminating conditions
 *    in loops, eg end() iterators 
 *    rowendi would mean a rowvi equal to the end() iterator
 */

/**
 * Only one output type must be chosen on the command line
 *  NUMBER	    the number of rows in solution found
 *  VERBOSE	    unformatted output for humans to see
 *  SOLUTION_ROWS   the rows in the solution, one per line
 */
enum output_type_t { NUMBER, VERBOSE, SOLUTION_ROWS };

/**
 * Only one algorithm must be chosen on the command line
 *  SET_COVER	    set cover
 *  VERTEX_COVER	    vertex cover
 */
enum algorithm_t { SET_COVER, VERTEX_COVER, IMPROVED_VERTEX_COVER };


/*****************************************************
 * Global variables for options, with default values *
 *****************************************************/
output_type_t output = SOLUTION_ROWS;
algorithm_t algorithm = SET_COVER;

bool output_set = false;	// not currently used
bool algorithm_set = false;	// not currently used

/**
 * utility function
 * print an error message to stderr and exit
 */
void error_exit (string error, int errcode=1)
{
    cerr << error << endl;
    exit(errcode);
}

/**
 * processes command line arguments. Subroutine that was
 * split out of main for readability
 * Uses global variables for saving options (algorithm, output)
 * @param   argc    taken directly from main
 * @param   argv    taken directly from main
 */
void parse_cli (int argc, char ** argv)
{
    /* strings recognized as specifying set cover */
    vector<string> set_cover_strings;
    set_cover_strings.push_back("sc");
    set_cover_strings.push_back("set");
    set_cover_strings.push_back("set-cover");

    /* strings recognized as specifying vertex cover */
    vector<string> vertex_cover_strings;
    vertex_cover_strings.push_back("vc");
    vertex_cover_strings.push_back("vertex");
    vertex_cover_strings.push_back("vertex-cover");

    /* strings recognized as specifying improved vertex cover */
    vector<string> improved_vertex_cover_strings;
    improved_vertex_cover_strings.push_back("ivc");
    improved_vertex_cover_strings.push_back("vc2");
    improved_vertex_cover_strings.push_back("vertex2");
    improved_vertex_cover_strings.push_back("vertex-cover2");
    improved_vertex_cover_strings.push_back("improved-vertex-cover");

    /* parse command line arguments
     * expected format: program [algorithm] [output], in either order
     * input is read via stdin */
    if (argc > 3) { // 0=prog, 1,2=algorithm,output
	cerr << "Warning: extra arguments beyond the second one will be ignored" << endl;
    }
    int end = std::max(3, argc);
    for (int i=1; i<end; i++) {
	string s(argv[i]);
	if (s.length() == 1) { // we have an output type option
	    if (s == "n") {
		output = NUMBER;
		output_set = true;
	    } else if (s=="v") {
		output = VERBOSE;
		output_set = true;
	    } else if (s=="r") {
		output = SOLUTION_ROWS;
		output_set = true;
	    } else {
		error_exit(string("Invalid option: ") + s);
		break;
	    }
	} else if (std::find(
		       set_cover_strings.begin(),
		       set_cover_strings.end(),
		       s
		   ) != set_cover_strings.end()
	) { // choose set cover
	    algorithm = SET_COVER;
	    algorithm_set = true;
	} else if (std::find(
		       vertex_cover_strings.begin(),
		       vertex_cover_strings.end(),
		       s
		   ) != vertex_cover_strings.end()
	) { // choose vertex cover
	    algorithm = VERTEX_COVER;
	    algorithm_set = true;
	} else if (std::find(
		       improved_vertex_cover_strings.begin(),
		       improved_vertex_cover_strings.end(),
		       s
		   ) != improved_vertex_cover_strings.end()
	) { // choose improved vertex cover
	    algorithm = IMPROVED_VERTEX_COVER;
	    algorithm_set = true;
	}
    }
}

/**
 * executes greedy algorithm to find a
 * column cover using the rows
 *
 * reads input from stdin, one row per line
 * all rows should be of equal length
 * WARNING:
 *  takes the dimensions from the length of the first row
 *  behavior is undefined if the first row is longer than the rest
 */
int main (int argc, char ** argv ) 
{
    parse_cli(argc, argv);

    /* get INPUT from stdin */

    // variables for storing input
    string line;
    vector<string> lines;

    while (getline(cin, line)) {    // read lines
	lines.push_back(line);
    }
    
    if (lines.empty()) /* no lines read */
	{ error_exit(string("No input")); }

    // sizes
    size_t ncols;
    size_t nrows;

    /* count the number of columns, using the first row
     * each '0' or '1' char counts as one column */
    ncols=0;
    string::iterator stritr = lines.front().begin();
    string::iterator strend = lines.front().end();
    while (stritr != strend) {
	if ( (*stritr == '0') || (*stritr == '1') ) { ++ncols;}
	++stritr;
    }
    // number of rows = number of lines
    nrows = lines.size();
    if (output == VERBOSE) cout << nrows << " by " << ncols << " matrix\n\n";

    /* convert the strings to a 2-dimensional array
     * implemented as a vector of vectors of ints */
    vector<vector<int> > matrix;

    vector<string>::iterator lineitr = lines.begin();
    vector<string>::iterator enditr = lines.end();

    while (lineitr != enditr) {
	vector<int> rowv;		// allocate a row vector

	// convert string to integers and push into rowv
	line = *lineitr;		// get copy of string
	string::iterator stritr = line.begin();
	string::iterator strend = line.end();
	while(stritr != strend) {
	    if (*stritr == '0') { rowv.push_back(0); }
	    else if ( *stritr == '1' ) { rowv.push_back(1); }
	    stritr++;
	}
	
	matrix.push_back(rowv);		// add copy of row vector into matrix
	++lineitr;			// next line
    }

    // records which columns are covered: 1 = covered, otherwise not covered
    int *cover = new int[ncols];

    list<int> solutions;		// indices of solution rows

    // initialize cover to all 0's
    //for (int *ptr = cover + (ncols-1); ptr >= cover; --ptr ) { *ptr = 0; }
    for (int i=0; i < ncols; ++i) { cover[i] = 0;}

    switch (algorithm) {
	case SET_COVER:
	    if (output == VERBOSE) cout << "Using Set Cover algorithm" << endl;
	    greedy_sc(matrix, nrows, ncols, cover, solutions);
	    break;
	case VERTEX_COVER:
	    if (output == VERBOSE) cout << "Using Vertex Cover algorithm" << endl;
	    greedy_vc(matrix, nrows, ncols, cover, solutions);
	    break;
	case IMPROVED_VERTEX_COVER:
	    if (output == VERBOSE)
		cout << "Using Improved Vertex Cover algorithm" << endl;
	    greedy_vc2(matrix, nrows, ncols, cover, solutions);
	    break;
	// there should never be a default case due to the default value
    }

    /* all done -- print solution set */
    switch (output) {
	case VERBOSE:
	    cout << solutions.size() << " solution rows:\n";
	case SOLUTION_ROWS:
	    { // braces are needed here b/c of the C++ standard
		list<int>::iterator s_itr = solutions.begin();
		list<int>::iterator s_end = solutions.end();
		while (s_itr != s_end) {
		    cout << setw(3) << *s_itr << ":\t" << lines.at(*s_itr) << '\n';
		    ++ s_itr;
		}
	    }
	    break;
	case NUMBER:
	    cout << solutions.size() << endl;
    } 

    /* clean up duty -- free up memory */
    delete[] cover;

    return 0;
}

